package Hot_100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * 解题思路
 *  先将各个区间，按照数组第一个元素进行升序排序
 *  （排序后方便进行合并，（只需要比较前一个区间的右边界和第二个区间的左边界就能知道是否有重叠；不排序合并很麻烦））
 */
public class T56_merge {
    public int[][] merge(int[][] intervals) {
        //对每个区间的第一个元素进行升序排序
        Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]);

        List<int[]> res = new ArrayList<>();
        for (int i = 0; i < intervals.length; i++) {
            int[] tmp = intervals[i];
            if (res.isEmpty() || res.get(res.size() - 1)[1] < intervals[i][0]) {
                //如果res为空或者最后一个区间的右边界小于要比较区间的左边界，两个区间不会出现重叠,直接加入即可
                res.add(tmp);
            } else if (res.get(res.size() - 1)[1] >= intervals[i][0]) {
                //  如果有重叠，取两个区间的最大右边界
                res.get(res.size() - 1)[1] = Math.max(res.get(res.size() - 1)[1], intervals[i][1]);
            }
        }
        return res.toArray(new int[res.size()][]);
    }
}
